﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution
{
    public TreeNode SortedArrayToBST(int[] nums)
    {
        if (nums is null || nums.Length == 0) return null;
        
        // 3个队列
        Queue<TreeNode> treeNodesQueue = new Queue<TreeNode>(); // 存放节点
        Queue<int> leftQueue = new Queue<int>(); // 存左边界
        Queue<int> rightQueue = new Queue<int>(); // 存右边界
        int left = 0, right = nums.Length - 1;
        leftQueue.Enqueue(left);
        rightQueue.Enqueue(right);
        TreeNode root = new TreeNode(0);
        treeNodesQueue.Enqueue(root);
        
        // 节点入队
        int mid;
        TreeNode node;
        while (leftQueue.Count > 0)
        {
            left = leftQueue.Dequeue();
            right = rightQueue.Dequeue();
            node = treeNodesQueue.Dequeue();

            mid = (left + right) / 2;
            node.val = nums[mid];
            
            // 有左区间
            if (left <= mid - 1)
            {
                leftQueue.Enqueue(left);
                rightQueue.Enqueue(mid - 1);
                node.left = new TreeNode(0);
                treeNodesQueue.Enqueue(node.left);
            }
            // 有右区间
            if (mid+1 <= right)
            {
                leftQueue.Enqueue(mid+1);
                rightQueue.Enqueue(right);
                node.right = new TreeNode(0);
                treeNodesQueue.Enqueue(node.right);
            }
        }

        return root;
    }

    public static void Main(string[] args)
    {
        int[] nums = [-10, -3, 0, 5, 9];

        Solution solution = new Solution();
        TreeNode rootNode = solution.SortedArrayToBST(nums);

        LevelOrderTraversa(rootNode);
    }

    private static void LevelOrderTraversa(TreeNode rootNode)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (rootNode is not null) queue.Enqueue(rootNode);
        TreeNode node;

        while (queue.Count > 0)
        {
            node = queue.Dequeue();
            
            // 访问节点
            Console.Write($"{node.val} ");
            if (node.left is not null) queue.Enqueue(node.left);
            if (node.right is not null) queue.Enqueue(node.right);
        }
        
    }

    private static TreeNode CreatBinaryTree(int?[] root)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (root is null || root.Length == 0 || root[0] is null) return null;
        
        // 根节点进队
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        TreeNode node;
        int i = 1;
        bool flag;
        while (queue.Count > 0)
        {
            flag = true;
            // 出队
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                flag = false;
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }
            
            if (++i >= root.Length) break;
            if (root[i] is not null)
            {
                flag = false;
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }

            if (++i >= root.Length) break;
            if (flag)
            {
                queue.Enqueue(node);
            }
        }

        return rootNode;
    }
}